package com.sheng.leetcode.year2025.month10.day03;

import org.junit.Test;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author by ls
 * @date 2025/10/14
 * <p>
 * 407. 接雨水 II<p>
 * <p>
 * 给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。<p>
 * <p>
 * 示例 1:<p>
 * 输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]<p>
 * 输出: 4<p>
 * 解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。<p>
 * <p>
 * 示例 2:<p>
 * 输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]<p>
 * 输出: 10<p>
 * <p>
 * 提示:<p>
 * m == heightMap.length<p>
 * n == heightMap[i].length<p>
 * 1 <= m, n <= 200<p>
 * 0 <= heightMap[i][j] <= 2 * 10^4<p>
 */
public class LeetCode0407 {

    @Test
    public void test() {
//        int[][] heightMap = {{1, 4, 3, 1, 3, 2}, {3, 2, 1, 3, 2, 4}, {2, 3, 3, 2, 3, 1}};
        int[][] heightMap = {{3, 3, 3, 3, 3}, {3, 2, 2, 2, 3}, {3, 2, 1, 2, 3}, {3, 2, 2, 2, 3}, {3, 3, 3, 3, 3}};
        System.out.println(new Solution().trapRainWater(heightMap));
    }
}

/**
 * 哪个格子的接水量，在一开始就能确定？
 * <p>
 * 最外面一圈的格子是无法接水的。
 * 假设 (0,1) 的高度是最外面一圈的格子中最小的，且高度等于 5，那么和它相邻的 (1,1)，我们能知道：
 * (1,1) 的水位不能超过 5，否则水会从 (0,1) 流出去。
 * (1,1) 的水位一定可以等于 5，这是因为 (0,1) 的高度是最外面一圈的格子中最小的，(1,1) 的水不会从其他地方流出去。
 * 我们从最外面一圈的格子开始。想象成一个木桶，最外面一圈格子的高度视作木板的高度。
 * <p>
 * 接着上面的讨论：
 * <p>
 * 如果 (1,1) 的高度 ≥5，那么 (0,1) 这块木板就没用了，我们去掉 (0,1) 这块木板，改用 (1,1) 这块木板。
 * 如果 (1,1) 的高度 <5，假设我们接的不是水，是水泥。那么把 (1,1) 的高度填充为 5，仍然可以去掉 (0,1) 这块木板，改用 (1,1) 这块（填充水泥后）高为 5 的木板水泥板。
 * 继续，从当前木板中，找到一根最短的木板。假设 (1,1) 是当前所有木板中最短的，那么其邻居 (1,2) 和 (2,1) 的水位就是 (1,1) 的高度，因为超过 (1,1) 高度的水会流出去。然后，去掉 (1,1) 这块木板，改用 (1,2) 和 (2,1) 这两块木板。依此类推。
 * <p>
 * 由于每次都要找最短的木板，所以用一个最小堆维护木板的高度。按照上述做法，不断循环，直到堆为空。
 * <p>
 * 作者：灵茶山艾府
 * 链接：<a href="https://leetcode.cn/problems/trapping-rain-water-ii/solutions/2998212/duan-ban-xiao-ying-pythonjavacgojsrust-b-39mp/">407. 接雨水 II</a>
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
class Solution {

    private static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

    public int trapRainWater(int[][] heightMap) {
        int m = heightMap.length, n = heightMap[0].length;
        // 需要计算给出的矩阵中，能围成多少水池
//        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    pq.add(new int[]{heightMap[i][j], i, j});
                    // 标记 (i,j) 访问过
                    heightMap[i][j] = -1;
                }
            }
        }

        int ans = 0;
        while (!pq.isEmpty()) {
            // 去掉短板
            int[] t = pq.poll();
            // minHeight 是木桶的短板
            int minHeight = t[0], i = t[1], j = t[2];
            for (int[] d : DIRS) {
                // (i,j) 的邻居
                int x = i + d[0], y = j + d[1];
                // (x,y) 没有访问过
                if (0 <= x && x < m && 0 <= y && y < n && heightMap[x][y] >= 0) {
                    // 如果 (x,y) 的高度小于 minHeight，那么接水量为 minHeight - heightMap[x][y]
                    ans += Math.max(minHeight - heightMap[x][y], 0);
                    // 给木桶新增一块高为 max(minHeight, heightMap[x][y]) 的木板
                    pq.add(new int[]{Math.max(minHeight, heightMap[x][y]), x, y});
                    // 标记 (x,y) 访问过
                    heightMap[x][y] = -1;
                }
            }
        }
        return ans;
    }
}
